# -*- coding:utf-8 -*-
from collections import deque
graph = {"A": ["B", "C"],
         "B": ["A", "C", "D"],
         "C": ["A", "B", "D", "E"],
         "D": ["B", "C", "E", "F"],
         "E": ["C", "D"],
         "F": ["D"]}


def bfs(_graph, s):
    queue = deque()
    queue.append(s)
    seen = set()
    seen.add(s)
    parent = {s: None}

    while len(queue) > 0:
        vertex = queue.popleft()
        nodes = _graph[vertex]
        for n in nodes:
            if n not in seen:  # 去重
                queue.append(n)
                seen.add(n)
                parent[n] = vertex

    return parent


parent_node = bfs(graph, "A")

print(parent_node)
node = "F"
bfs_result = []
while node is not None:
    bfs_result.append(node)
    node = parent_node[node]

print(sorted(bfs_result))
